package main

//TODO : 线性结构-----线性表的链式存储(链表)

type List *LNode

type LNode struct {
	Data interface{}
	Next List
}

//TODO : 初始化(初始化一个空线性表)
func MakeEmpty() (list List) {
	list = new(LNode)
	list.Next = nil
	return list
}

//TODO : (求表长)返回线性表L的长度n
func Length(list List) (l int) {
	var p List = list
	l = 0
	for {
		p = p.Next
		if p == nil {
			break
		}
		l++
	}
	return l
}

//TODO : (按序号查找)根据位序K, 返回相应元素 -- 按值查找类似
func FindKth(list List, k int) (list2 List) {
	p := list
	i := 1

	for {
		//todo : 弄成一个if
		if p.Next == nil || i > k {
			list2 = nil
			return
		}
		if i == k {
			list2 = p
			return
		}
		p = p.Next
		i++
	}
}

//TODO : 插入(在位序k前插入一个新元素v)
func Insert(list List, k int, v interface{}) (list2 List) {
	if k == 1 {
		list2 = &LNode{Data: v, Next: list}
		return
	}
	p := FindKth(list, k-1)
	if p == nil {
		return nil
	} else {
		p1 := &LNode{Data: v, Next: p.Next}
		p.Next = p1
		return p
	}
}

//TODO : (删除)删除指定位序k的元素
func Delete(list List, k int) (list2 List) {
	if k == 1 {
		list2 = list.Next
		return
	}

	p := FindKth(list, k-1)
	if p == nil || p.Next == nil {
		return nil
	} else {
		p1 := p.Next
		p.Next = p1.Next
		//todo : go 自动释放p1的内存空间 ??
		return p
	}
}
